#include <vector>
#include <iostream>

using namespace std;

vector<vector<int>> sudoku {
  {5, 3, 0, 0, 7, 0, 0, 0, 0},
  {6, 0, 0, 1, 9, 5, 0, 0, 0},
  {0, 9, 8, 0, 0, 0, 0, 6, 0},
  {8, 0, 0, 0, 6, 0, 0, 0, 3},
  {4, 0, 0, 8, 0, 3, 0, 0, 1},
  {7, 0, 0, 0, 2, 0, 0, 0, 6},
  {0, 6, 0, 0, 0, 0, 2, 8, 0},
  {0, 0, 0, 4, 1, 9, 0, 0, 5},
  {0, 0, 0, 0, 8, 0, 0, 7, 9}
};

// 在 board 的 row 行，col 列的位置 value 是否合法
// isValidateAtPosition(3, 0, 1, sudoku)
bool isValidateAtPosition(int value, int row, int col, vector<vector<int>> &board) {
  // 1.在行内寻找 value，小数组里找 value

  // 2.在列内找 value，遍历棋盘，查找每个小数组的第 col 个成员

  // 3.在每一个小棋盘里查找
  // 给定 (row,col)，如何在它所属的小棋盘里查找 value
  // 起始行位置 row/3 * 3
  // 起始列位置 col/3 * 3

  return true;
}

// 从 board 的第 row 行，第 col 列开始解数独
bool solve(int row, int col, vector<vector<int>> board) {
  // 这里，我们要先检查当前列是否已经到末尾
  // 如果到末尾，我们就先换行。
  if (col == board[row].size()) {
    ++row;
    col = 0;
  }
  
  if (row == board.size()) {
    // 然后再检查 row，如果已经遍历完所有行，此时调用 solve 传递的参数 board
    // 就是最终求解的数独，我们在这里，打印 board 即可。
    for (int m = 0; m < 9; ++m) {
      for (int n = 0; n < 9; ++n) {
        cout << board[m][n] << " ";
      }
      cout << endl;
    }

    return true;
  }
  
  if (board[row][col] == 0) {
    // 这里进行的 for 循环，是为了要在 row,col 位置，从 1-9 尝试插入数字
    // 所以 i 应该从 1 开始。
    for (int i = 1; i < 10; ++i) {
      vector<vector<int>> copy = board;
      if (isValidAtPosition(i, row, col, board)) {
        copy[row][col] = i;
        
        if (solve(row, col + 1, copy)) {
          return true;
        }
      }
    }
  }

  return solve(row, col + 1, board);
}

int main(int argc, char const *argv[])
{
  /* code */
  return 0;
}
